package day_2023_7_to_10;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author haomin
 * @date 2023/07/25 23:16
 **/
public class Day_7_25 {
    class MaxQueue {
        Deque<Integer> q1;
        Deque<Integer> q2;

        public MaxQueue() {
            q1 = new LinkedList<>();
            q2 = new LinkedList<>();
        }

        public int max_value() {
            return q2.isEmpty() ? -1 : q2.peek();
        }

        public void push_back(int value) {
            q1.offer(value);
            while(!q2.isEmpty() && q2.peekLast() < value) q2.pollLast();
            q2.offer(value);
        }

        public int pop_front() {
            if (q1.isEmpty()) return -1;
            int value = q1.poll();
            if (q2.peek() == value) q2.poll();
            return value;
        }
    }
    class Solution {
        public boolean validateStackSequences(int[] pushed, int[] popped) {
            Deque<Integer> s = new LinkedList<>();
            int i = 0, j = 0;
            while(i < pushed.length) {
                s.push(pushed[i]);
                i++;
                while(!s.isEmpty() && s.peek() == popped[j]) {
                    s.pop();
                    j++;
                }
            }
            return s.isEmpty();
        }
    }
}